The unprecedented growth of data collection has made protecting user privacy a central challenge. Local Differential Privacy (LDP) offers a compelling solution, enabling the analysis of population-level statistics without exposing any individual's raw data--even to the aggregator [Dwork et al., 2006, Kasiviswanathan et al., 2011]. In this model, each user perturbs their own data before transmission, ensuring that only randomized reports reach the curator. This paradigm has moved well beyond theory, with large-scale deployments at Google [Erlingsson et al., 2014], Microsoft [Ding et al., 2017], and Apple [Differential Privacy T eam, Apple, 2017, Thakurta et al., 2017]. Most research on LDP, however, rests on two simplifying assumptions: that all users share a uniform privacy guarantee (ε) and that error bounds only need to hold in expectation or just with a constant probability . In this work, we move beyond this idealized model to study two crucial and more realistic variants of LDP .

Three strands of prior work motivate this study: minimax-quantile bounds restricted to non-interactive estimation; unified interactive analyses that focus on expected risk rather than risk level specific quantile bounds; and high-probability bandit bounds that still lack a quantile-specific toolkit for general interactive protocols. To close this gap, within the interactive statistical decision making framework, we develop high-probability Fano and Le Cam tools and derive risk level explicit minimax-quantile bounds, including a quantile-to-expectation conversion and a tight link between strict and lower minimax quan-tiles. Instantiating these results for the two-armed Gaussian bandit immediately recovers optimal-rate bounds. Index T erms-- information theory, learning theory 1. INTRODUCTION The concept of minimax risk has become a staple in learning theory and statistics [1-3]. In interactive or online learning settings, the minimax risk is often replaced by its counterpart, the minimax regret.

The minimax risk is often considered as a gold standard against which we can compare specific statistical procedures. Nevertheless, as has been observed recently in robust and heavy-tailed estimation problems, the inherent reduction of the (random) loss to its expectation may entail a significant loss of information regarding its tail behaviour. In an attempt to avoid such a loss, we introduce the notion of a minimax quantile, and seek to articulate its dependence on the quantile level. To this end, we develop high-probability variants of the classical Le Cam and Fano methods, as well as a technique to convert local minimax risk lower bounds to lower bounds on minimax quantiles. To illustrate the power of our framework, we deploy our techniques on several examples, recovering recent results in robust mean estimation and stochastic convex optimisation, as well as obtaining several new results in covariance matrix estimation, sparse linear regression, nonparametric density estimation and isotonic regression. Our overall goal is to argue that minimax quantiles can provide a finer-grained understanding of the difficulty of statistical problems, and that, in wide generality, lower bounds on these quantities can be obtained via user-friendly tools.